/************************************************************
 * DS_ALGORITHM.H                                  14.09.2006
 *
 * .
 ************************************************************/
#ifndef _DS_ALGORITHM_H_
#define _DS_ALGORITHM_H_

#pragma once

#include "ds/ds_comm.h"
#include "ds/ds_string.h"
#include "ds/ds_vector.h"
//#include "ds/ds_custom_printf.h"
#include "m3d\m3d.h"

// SNC compilation error fix
FORCE_INLINE int Hash(int v, UINT a, UINT b);
FORCE_INLINE int Hash(const char * ptr, UINT a, UINT b);
FORCE_INLINE int Hash(const void * ptr, UINT a, UINT b);

// String forward declaration
template <class CH> class dsTSTRING;
typedef dsTSTRING<char>    dsSTRING;

struct m3dV;
class m3dMATR;
class m3dBOX;
class m3dOBB;

// HELPER MACROSES
#define DS_MAKE_CMP(NAME, TYPE, BODY) \
   struct NAME { \
      int cmp(TYPE a, TYPE b) const { \
         BODY; \
      } \
   };

namespace ds {

const unsigned int BIG_PRIME = 1431655777u;

class CMP {
public:
   template <class T1, class T2>
   static inline int cmp(const T1 & a, const T2 & b)
   { return a < b ? -1 : b < a ? 1 : 0; }

   template <class T1, class T2>
   static inline bool equals(const T1 & a, const T2 & b)
   { return a == b; }
};

template <class T>
class CMP_T {
public:
   static inline int cmp(const T & a, const T & b)
   { return a < b ? -1 : b < a ? 1 : 0; }

   static inline bool equals(const T & a, const T & b)
   { return a == b; }
};

struct HASH {
	template <class T>
	static inline int hash(const T & p, UINT a, UINT b) { return Hash(p, a, b); }
};

// BUBBLE SORT (for gourmets)
template <class ITER, class CMP>
inline void BubbleSort(ITER begin, ITER end, const CMP & cmp);

template <class ITER>
inline void BubbleSort(ITER begin, ITER end)
{ BubbleSort(begin, end, dsCMP()); }

/*************************************************************
* Sort()
* 
*************************************************************/
template <class ITER, class CMP>
inline void Sort(ITER first, ITER last, const CMP & cmp);

template <class ITER>
inline void Sort(ITER first, ITER last)
{ Sort(first, last, dsCMP()); }

template <class TYPE>
inline void Sort(dsVECTOR<TYPE> & arr)
{ Sort(arr.Begin(), arr.End()); }

template <class TYPE, class CMP>
inline void Sort(dsVECTOR<TYPE> & arr, const CMP & cmp)
{ Sort(arr.Begin(), arr.End(), cmp); }

template <class TYPE, class CMP>
inline void SortUsingPermutation(dsVECTOR<TYPE> & arr, const CMP & cmp);

/**************************************************************************
* RemoveDuplicates()                                                      *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
int RemoveDuplicates(dsVECTOR<T> & arr, const CMP & cmp);

template <class T>
int RemoveDuplicates(dsVECTOR<T> & arr)
{ return RemoveDuplicates(arr, dsCMP()); }

/*************************************************************************
* Method: ds<T, CMP>::IsSorted
*
*************************************************************************/
template <class T, class CMP>
inline bool IsSorted(const dsVECTOR<T> & a, const CMP & cmp);

template <class T>
inline bool IsSorted(const dsVECTOR<T> & a)
{ return IsSorted(a, dsCMP()); }

template <class T, class CMP>
inline bool IsSortedUniq(const dsVECTOR<T> & a, const CMP & cmp);

template <class T>
inline bool IsSortedUniq(const dsVECTOR<T> & a)
{ return IsSortedUniq(a, dsCMP()); }

/*************************************************************************
* Method: ds<CMP>::MergeSorted
*
*************************************************************************/
template <class T, class CMP>
void MergeSorted(dsVECTOR<T> & res, const dsVECTOR<T> & a, dsVECTOR<T> & b, const CMP & cmp);

template <class T>
void MergeSorted(dsVECTOR<T> & res, const dsVECTOR<T> & a, dsVECTOR<T> & b)
{ MergeSorted(res, a, b, dsCMP()); }

template <class T, class CMP>
void MergeSortedUniq(dsVECTOR<T> & res, const dsVECTOR<T> &arr1, const dsVECTOR<T> &arr2, const CMP &cmp);

template <class T>
void MergeSortedUniq(dsVECTOR<T> & res, const dsVECTOR<T> &arr1, const dsVECTOR<T> &arr2)
{ MergeSortedUniq(res, arr1, arr2, dsCMP()); }

/**************************************************************************
* Reverse()                                                               *
*                                                                         *
**************************************************************************/
template <class ITER>
void Reverse(ITER begin, ITER end);

template <class T>
void Reverse(dsVECTOR<T> & arr)
{ Reverse(arr.Begin(), arr.End()); }

/**************************************************************************
* Substract()                                                             *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
int Substract(dsVECTOR<T> & left, dsVECTOR<T> & right, const CMP & cmp);

template <class T>
int Substract(dsVECTOR<T> & left, dsVECTOR<T> & right)
{ return Substract(left, right, dsCMP()); }

/**************************************************************************
* Append()                                                                *
*                                                                         *
**************************************************************************/
template <class T>
void Append(dsVECTOR<T> & left, const dsVECTOR<T> & right, int start = 0, int count = -1);

// using memcpy
template <class T>
void AppendFast(dsVECTOR<T> & left, const dsVECTOR<T> & right, int start = 0, int count = -1);

template <class T>
void Shuffle(dsVECTOR<T> & arr);


/**************************************************************************
* IsIntersect()                                                           *
*                                                                         *
**************************************************************************/
template <class T, class CMP>
bool IsIntersect(const dsVECTOR<T>& v1, const dsVECTOR<T>& v2, const CMP& cmp);

template <class T>
bool IsIntersect(const dsVECTOR<T>& v1, const dsVECTOR<T>& v2)
{ return IsIntersect(v1, v2, dsCMP()); }


//////////////////////////////////////////////////////////////////////////
// Sort elements with id in range 0..n-1 
template <class T>
struct CMP_SWAP_0_N_BASE {
   template <class ITER>
   void swap(ITER a, ITER b) const {
      T tmp = a;
      a = b;
      b = tmp;
   }
};

template <class T>
struct CMP_SWAP_0_N_REORDER {
   dsVECTOR<T> & toReorder;

   CMP_SWAP_0_N_REORDER(dsVECTOR<T> & toReorder)
      : toReorder(toReorder)
   {}

   int value(int * val) const {
      return *val;
   }

   void swap(int * a, int * b) const {
      int tmp = *a;
      *a = *b;
      *b = tmp;

      dsSwap(toReorder[*a], toReorder[*b]);
   }
};

template <class ITER, class CMP_SWAP_0_N>
inline void Sort_0_n(ITER first, ITER last, const CMP_SWAP_0_N & cmp);

/*************************************************************
 * CheckPrime()
 * 
 *************************************************************/
bool CheckPrime(int number);

/*************************************************************
* FindPrime()
* 
*************************************************************/
int FindPrime(int minPrime);

/**************************************************************************
* MemHash()                                                               *
*                                                                         *
**************************************************************************/
int MemHash(const void * mem, int length);

/*************************************************************
* ByteReorder()
* 
*************************************************************/
void ByteReorder (BYTE *data, int size, int reorderGain);

/*************************************************************
* FindNonSorted
* 
*************************************************************/
template <class CMP, class ITER, class VAL>
ITER FindNonSorted (const ITER & begin, const VAL & val);

template <class ITER, class VAL>
ITER FindNonSorted (const ITER & begin, const VAL & val)
{ return FindNonSorted<CMP> (begin, val); }


inline int FindNonSorted(const char * array[], int length, const char * val);

template <class T, class VAL>
int FindNonSorted(const T * array, int length, const VAL & val);

template <class T, class VAL>
int FindNonSorted(const dsVECTOR<T> & array, const VAL & val)
{ return FindNonSorted(array.Begin(), array.Length(), val); }

template <class T, class CMP>
int FindNonSortedMaxIdx(const dsVECTOR<T> & array, const CMP & cmp);


/*************************************************************
* FindSortedFirst
* 
*************************************************************/
template <class T, class V>
int FindSortedFirst(const dsVECTOR<T> & array, const V & val)
{ return FindSortedFirst(array, val, dsCMP()); }

template <class T, class V, class CMP>
int FindSortedFirst(const dsVECTOR<T> & array, const V & val, const CMP & cmp)
{ return FindSortedFirst(array.Begin(), array.Length(), val, cmp); }

template <class T, class V>
int FindSortedFirst(const T * array, int length, const V & val)
{ return FindSortedFirst(array, length, val, dsCMP()); }

template <class T, class V, class CMP>
int FindSortedFirst(const T * array, int length, const V & val, const CMP & cmp);

template <class T, class V>
int FindSortedLast(const dsVECTOR<T> & array, const V & val)
{ return FindSortedLast(array, val, dsCMP()); }

template <class T, class V, class CMP>
int FindSortedLast(const dsVECTOR<T> & array, const V & val, const CMP & cmp)
{ return FindSortedLast(array.Begin(), array.Length(), val, cmp); }

template <class T, class V, class CMP>
int FindSortedLast(const T * array, int length, const V & val, const CMP & cmp);

#define QUICK_HASH_BUILDER

class HASH_BUILDER {
public:
	HASH_BUILDER(int a, int b)
		: cur(), a(UINT64(a)), b(UINT64(b)), count()
	{}

	FORCE_INLINE void			Add				(int value) {
		CASSERT(ds::BIG_PRIME < 1u << 31);

#ifdef QUICK_HASH_BUILDER
		cur ^= ((UINT64)value * a + b) << count;
		count = (count + 1) & 0x07;
#else
		STRONG_ASSERT(cur < ds::BIG_PRIME);
		cur <<= 32;
		cur += (UINT64)value * a;
		if (cur >= ds::BIG_PRIME) {
			cur %= ds::BIG_PRIME;
		}
#endif
	}

	FORCE_INLINE void			Add				(BYTE value) {
#ifdef QUICK_HASH_BUILDER
		cur ^= ((UINT64)value * a + b) << count;
		count = (count + 1) & 0x07;
#else
		STRONG_ASSERT(cur < ds::BIG_PRIME);
		cur <<= 8;
		cur += (UINT64)value * a;
		if (cur >= ds::BIG_PRIME) {
			cur %= ds::BIG_PRIME;
		}
#endif
	}

	FORCE_INLINE void			Add				(const void * buf, int length) {
		const int fours = length >> 2;
		for (int i=0; i<fours; ++i) {
			Add(((int *)buf)[i]);
		}
		for (int i=fours << 2; i < length; ++i) {
			Add(((BYTE *)buf)[i]);
		}
	}

	// extensible method for custom types
	template <class T>
	FORCE_INLINE void			AddEx				(const T & val) {
#ifndef _AP_PS3
		CASSERT(false);
#else
		STRONG_ASSERT(!"Dummy functions");
#endif
	}

	int							Value				(void) const {
#ifdef QUICK_HASH_BUILDER
		return int(cur % ds::BIG_PRIME);
#else
		STRONG_ASSERT(cur < ds::BIG_PRIME);
		return int( (cur + b) % ds::BIG_PRIME );
#endif
	}

private:
	UINT64			cur;
	UINT64			a, b;
	int				count;
};

template <class T>
struct APPENDER_T {
   T & val;
   APPENDER_T(T & val) : val(val) {}

   template <class T0>
   APPENDER_T<T> & operator += (const T0 & v) {
      val += v;
      return *this;
   }

   template <class T0>
   APPENDER_T<T> & operator , (const T0 & v) { return *this += v; }
};

template <class T>
struct APPENDER_T<dsVECTOR<T> > {
   dsVECTOR<T> & val;
   APPENDER_T(dsVECTOR<T> & val) : val(val) {}

   APPENDER_T<dsVECTOR<T> > & operator += (const T & v) {
      val.PushBack(v);
      return *this;
   }

   APPENDER_T<dsVECTOR<T> > & operator , (const T & v) { return *this += v; }
};

template <class T>
APPENDER_T<T> APPENDER(T & val)
{ return APPENDER_T<T>(val); }

template <class ITER, class CMP> 
ITER Min(ITER begin, ITER end, const CMP & cmp);

template <class ITER>
ITER Min(ITER begin, ITER end) { return Min(begin, end, ds::CMP()); }

/******************************************************************************/
/* ds<T>::FillLinear
/*
/******************************************************************************/
template <class T>
inline void FillLinear(dsVECTOR<T> & array, int count, const T & start, const T & step);

template <class T>
inline void FillLinear(dsVECTOR<T> & array, int count)
{ FillLinear<T>(array, count, 0, 1); }

/******************************************************************************/
/* ds<T>::ApplyPermutation
/*
/******************************************************************************/
template <class T>
inline void ApplyPermutation(dsVECTOR<T> & array, const dsVECTOR<int> & permutation);

template <class T>
inline void ApplyPermutation(const dsVECTOR<T> & array, const dsVECTOR<int> & permutation, dsVECTOR<T> & res);

dsSTRING ToString(int val);
dsSTRING ToString(long val);
dsSTRING ToString(unsigned int val);
dsSTRING ToString(unsigned long val);
dsSTRING ToString(float val);
dsSTRING ToString(const m3dV& val);
dsSTRING ToString(const m3dMATR& matr);
dsSTRING ToString(const m3dBOX& box);
dsSTRING ToString(const m3dOBB& box);
dsSTRING ToString(const void * ptr);

struct SEARCH_PAIR {
   int lo, mid, hi;

   SEARCH_PAIR(void);
   void Init(int lo, int hi);
   bool IsDone(void) const;
   void Step(bool result);
};

#include "ds_algorithm.hpp"

} // namespace ds

/*************************************************************
* Hash()
* 
* place it to global namespace
*************************************************************/
FORCE_INLINE int Hash(int v) { return v; }
FORCE_INLINE int Hash(int v, UINT a, UINT b) { ds::HASH_BUILDER r(a, b); r.Add(v); return r.Value(); }

/**************************************************************************
* Ptr2Int()                                                               *
*                                                                         *
**************************************************************************/
#ifdef _AP_PC
typedef _W64 int int_ptr;
#else
typedef int int_ptr;
#endif

namespace ds {

/**************************************************************************
* Ptr2Int()                                                               *
*                                                                         *
**************************************************************************/
CASSERT(sizeof(int) >= sizeof(void *));
template <class T>
int Ptr2Int(T * ptr)
{ return (int)(int_ptr)ptr; }

/**************************************************************************
* Int2Ptr()                                                               *
*                                                                         *
**************************************************************************/
CASSERT(sizeof(int) >= sizeof(void *));
template <class T>
T* Int2Ptr(int ptr)
{ return (T*)(int_ptr)ptr; }

/**************************************************************************
* CountFormatArguments()                                                  *
* type: use 's' to count %s parameters                                    *
*                                                                         *
* TODO: support formats like %.2f                                         *
**************************************************************************/
int CountFormatArguments(const char * format, int type = -1);

}

/**************************************************************************
* Hash()                                                                  *
*                                                                         *
**************************************************************************/
FORCE_INLINE int Hash(const void * ptr) { return ds::Ptr2Int(ptr); }
FORCE_INLINE int Hash(const void * ptr, UINT a, UINT b) { return Hash(ds::Ptr2Int(ptr), a, b); }

/*************************************************************
* Hash()
* 
*************************************************************/
FORCE_INLINE int Hash(const char * ptr, UINT a, UINT b) { ds::HASH_BUILDER r(a, b); r.Add((BYTE *)ptr, (int)strlen(ptr)); return r.Value(); }
FORCE_INLINE int Hash(char * ptr, UINT a, UINT b)       { ds::HASH_BUILDER r(a, b); r.Add((BYTE *)ptr, (int)strlen(ptr)); return r.Value(); }

FORCE_INLINE int Hash(const dsSTRING & str) { return ds::MemHash(str.CStr(), str.Length()); }
FORCE_INLINE int Hash(const dsSTRING & str, UINT a, UINT b) { ds::HASH_BUILDER r(a, b); r.Add(str.CStr(), str.Length()); return r.Value(); }

namespace ds {
   template <>
   inline void HASH_BUILDER::AddEx<dsSTRING> (const dsSTRING & p) {
      Add(p.CStr(), p.Length());
   }

   template <class T>
   dsSTRING ToString(const dsVECTOR<T> & array) {
      if (array.IsEmpty()) {
         return "[]";
      }

      dsSTRING res = "[";
      for (int k = 0; k < array.Length(); ++k) {
         res += ds::ToString(array[k]);
         if (k + 1 == array.Length()) {
            res += "]";
         } else {
            res += ", ";
         }
      }

      return res;
   }
};

#endif // _DS_ALGORITHM_H_
